A best-first search is an iterative search that at each iteration tries to extend the partial solution with the best estimated cost. Best-first searches have often been used to identify the shortest path between source and target points in a multi-point search space. One such best-first search is the A* search. To identify a path between source and target points, the A* search starts one or more paths from the source and/or target points. It then iteratively identifies one or more path expansions about the lowest cost path, until it identifies a path that connects the source and target points. The typical cost of a path expansion in an A* search is an {circumflex over (F)} cost, which is the cost of the path leading up to the path expansion plus an estimated cost of reaching a target point from the path expansion.
FIGS. 1–6 provide an example of an A* path search that uses such an {circumflex over (F)} cost. In this example, the search process has to find the shortest path between a source point 105 and a target point 110 in a region 120. The source and target points are part of a multi-point grid 115 that is imposed over the region.
As shown in FIG. 2, the search process initially identifies four path expansions from the source point 105 to four points 202–208 that neighbor the source point in the Manhattan directions. In FIGS. 2–6, the search process represents each path expansion by using a path identifier, called a “drop.” More specifically, the search process represents each path expansion from one grid point (a start point) to another point (a destination point) by (1) specifying a drop, (2) associating the drop with the expansion's destination point, and (3) defining the specified drop's previous drop to be the drop of the expansion's start point. Drops allow the search to keep track of the paths that it explores.
The search process specifies four drops 210–216 for the expansions to the four points 202–208, as illustrated in FIG. 2. It also specifies a drop 218 for the source point 105. The source point drop 218 is the previous drop of drops 210–216. The source point drop's previous drop is null, as it is the first drop in the path search.
For each drop 210–216, the search process computes an F cost based on the following formula:{circumflex over (F)}=G+Ĥ. where (1) G specifies the cost of a path from the source point to the drop's grid point through the sequence of expansions that led to the drop, and (2) Ĥ specifies the estimated lower-bound cost from the drop's grid point to the target point. When computed in this manner, the {circumflex over (F)} cost of a drop is the estimated cost of the cheapest path that starts at the source point, traverses through the sequence of expansions that led to the drop, and traverses from the drop to the target point.
To simplify the description of the example illustrated in FIGS. 1–6, the distance between each pair of horizontally or vertically adjacent grid points is 1. Accordingly, in FIG. 2, the G cost of each drop 210–216 is 1, as the grid point of each of these drops is one grid unit away from the source point. In FIGS. 2–6, a drop's Ĥ cost is computed as the Manhattan distance between the drop's point and the target point. Hence, the Ĥ cost of drops 210, 212, 214, and 216 are respectively one, three, three, and three, as these distances are respectively the Manhattan distances of the points of these drops from the target point.
After costing these drops, the search process stores the drops 210–216 in a priority queue that is sorted based on their {circumflex over (F)} costs. It then retrieves the drop with the lowest {circumflex over (F)} cost from the priority queue. This drop is drop 210. Since this drop's corresponding point (i.e., point 202) is not the target point, the search process then identifies a path expansion from the retrieved drop's point 202 to point 305. As shown in this figure, this expansion is the only viable expansion from the retrieved drop's point 202 as the search has previously reached all other unblocked neighboring grid points (i.e., the grid points that are not blocked by an obstacle 315) through less expensive paths. The search process specifies a drop 310 for this expansion, and computes this drop's G, Ĥ, and {circumflex over (F)} costs, which are respectively 2, 2, and 4. It then stores this specified drop in the priority queue.
After storing drop 310 in the priority queue, the search process might retrieve either drop 310, drop 212, or drop 214 from the priority queue, as each of these drops has an F cost of 4. However, if the search process retrieved drop 310, it will not expand from this drop to its neighboring points that are not blocked by obstacle 315 since all these neighboring points were previously reached less expensively. Also, if the search process retrieves drop 214, it will identify drops that will be more expensive than drop 212.
When the search process retrieves drop 212 from the priority queue, it checks whether this drop's point is the target point. When it discovers that it is not, the process (1) identifies expansions to three neighboring points 402–406 about this drop's point, as shown in FIG. 4, (2) specifies three drops 408–412 for the three identified expansions, as shown in FIG. 4, (3) computes each specified drop's G, Ĥ, and {circumflex over (F)} costs, (4) defines each specified drop's previous drop (which in this case is drop 212), and (5) stores each newly specified drop in the priority queue based on its F cost.
Next, as illustrated respectively in FIGS. 5 and 6, the search process performs these six operations first for drop 408 and then for drop 510, since these two drops are the ones with the lowest F costs during the next two iterations of the search process. As illustrated in FIG. 5, the drop 510 is specified for an expansion about drop 408's point 402.
As shown in FIG. 6, one of the expansions about drop 510 reaches the point 110. The search process creates, costs, and stores a drop 615 for this expansion. It then retrieves this drop in its next iteration, and then realizes that this drop's point is the target point. Accordingly, at this juncture, it terminates its path search operation. It then commences a path-embedding, back-trace operation that uses the previous-drop references of the drops 615, 510, 408, 212, and 218 to identify the sequence of drops that reached the target point 110 from the source point 105. This operation embeds a path along the grid points associated with the identified sequence of drops. FIGS. 7 and 8 illustrate the back-trace operation and the resulting embedded path.
The A* search is not suitable for finding the lowest-cost path in a graph with non-zero dimensional states. This is because the A* search computes a single cost value for the expansion to any state in the graph, while the actual cost can vary across a non-zero dimensional state. Accordingly, there is a need for a path search process that can identify the lowest-cost path in a graph with non-zero dimensional states.